The present invention relates to data processing networks and, more particularly, to a method of selecting data transmission rates for a network of receivers having heterogeneous reception bandwidth.
The increased capacity and flexibility of the Internet and other data processing networks have increased the practicality and popularity of delivering data processing services over these networks. However, data transmission over networks connecting large numbers of receivers can be problematic. For example, many applications, such as multimedia applications, require relatively high bandwidth. A 25 second long, 320×240 Quick Time video may require 2.3 MB, approximately equivalent to one thousand screens of textual data. In addition, the data stream for a multimedia application is often characterized by bursts of data and, unless the transmission rate is smoothed, the limited reception buffers of data receivers may overflow or underflow causing loss of data and poor quality service. Second, many applications require real-time data delivery. If the network is congested and delivery is delayed, the data becomes obsolete and will be dropped. Some applications, such as real time video and voice transmission, are characterized by a level loss tolerance where the quality of the service is degraded by data loss but may still be tolerable to the user. Other applications may rely on forward error correction (FEC) or data retransmission separate from the usual multi-cast transmission to recover from data losses. However, attempts to retransmit lost data packets can aggravate network congestion producing additional data loss.
On the other hand, the limited bandwidth of data processing networks is typically shared by many users utilizing data receivers with differing local reception bandwidth. For example, a receiver connected to the Internet may be connected through a 28.8 Kbps modem, a 56 Kbps modem, a digital subscriber line (DSL) (typically, 256 Kbps bandwidth), a cable modem, or a local area network (LAN) connection (10 Mbps or greater bandwidth). While the network connection is one source of bandwidth limitation for a receiver, the bandwidth of one or more receivers may also be limited by a bottleneck link in the network path connecting the receivers and the data transmitter. Further as a result of congestion, the bandwidth of the network links in the path to the receiver may vary substantially throughout a typical network session.
Variation in local reception bandwidth is a frustrating factor for unicast data transmission where one server and one client exchange data. However, multimedia applications are often delivered simultaneously to many users by multicast transmission. In a multicast delivery, a server transmits a plurality of data streams to a plurality of multicast group addresses. An individual receiver can subscribe to a multicast group address providing a maximum data rate not exceeding the receiver's local reception bandwidth and, therefore, the highest quality service available to the receiver considering its limited local bandwidth. Allocating data transmission rates to preserve the quality of the service and optimize the data rate for each receiver, while avoiding network congestion, is a difficult task.
Layered encoding is a technique providing a plurality of incrementally encoded data streams. A base layer is transmitted at a rate providing good service for receivers having a bandwidth at the lower end of the range supported by the service. Data is also encoded in one or more additional or enhancement layers that can be incrementally combined by receivers having greater reception bandwidth to provide progressively higher levels of quality for the application. For example, a video base layer might be encoded at a minimum data rate to provide acceptable video at a receiver connected to the network with a 56 Kbps modem. Each additional enhancement layer provides improved video quality but requires an incremental increase in bandwidth and is thus suitable only for receivers having a bandwidth greater than 56 Kbps, for examples, receivers with DSL or Ethernet connections. Receiver-driven layered multicast provides a mechanism for a receiver to subscribe to one or more enhancement layers as permitted by the receiver's limited reception bandwidth thereby maximizing the quality at each of the receivers of the heterogeneous network. However, the data processing capabilities of the server and, therefore the number of layers, are limited and it is desirable to transmit layers at data rates that are optimized to provide the highest quality to the greatest number of receivers.
A similar data transmission technique encodes multiple separate data streams. Typically, each data stream is encoded at a data rate targeted to a bandwidth suitable for one of the network connection types. However, the actual reception bandwidth of a data receiver may be considerably less than the ideal bandwidth for the receiver's connection type and the local reception bandwidth varies with time during the network session.
To avoid underutilization of higher capacity paths to subgroups of receivers of a multi-cast transmission, Jiang et al., ON THE USE OF DESTINATION SET GROUPING TO IMPROVE INTER-RECEIVER FAIRNESS OF MULTICAST ABR SESSIONS, Proceedings of IEEE Infocom '00, March 2000, have proposed partitioning the group of receivers into subgroups (destination set grouping (DSG)) maximizing inter-receiver fairness for a network session. Inter-receiver fairness is a measure quantifying the underutilization of a plurality of transmission paths when data is transmitted at a rate minimizing data loss on the path of least bandwidth. However, DSG requires the server to periodically poll connected routers which, in turn, poll additional connected routers to determine an isolated data rate for each receiver. The server then groups the receivers utilizing a grouping heuristic employing a plurality of criteria. However, the system is complex and requires considerable computation and additional network communication.
Smith et al., BANDWIDTH ALLOCATION FOR LAYERED MULTICASTED VIDEO, Proc. of the IEEE International Conference on Multimedia Computing and Systems (ICMCS), Florence, Italy, June 1999 have proposed a layered multicast control protocol (LMCP) in which the sender stripes the video signal across multiple multicast channels and each receiver adds or drops channels to meet its individual needs. Each receiver provides feedback to the sender by estimating a bottleneck rate based on a quantity of data lost and an elapsed time from the beginning of a channel joining experiment and the sender uses the feedback to adjust the transmission rate for each channel. Three algorithms were proposed for determining data transmission rates. A first algorithm utilized a dynamic programming solution to determine an optimal set of transmission rates but, according to the authors, was sufficiently complex as to be “impractical” for a large number of receivers. A divide and conquer algorithm which produces transmission rates comparable to those computed with the first algorithm was also proposed. While complex, the method was said to be useful for “reasonable” numbers of channels and receivers. A third algorithm selected transmission rates based on a fixed percentile which depended on the number of channels. This algorithm was not adaptive or dynamic and, according to the authors, did not perform well when the receiver bottleneck rates had certain distributions.
What is desired therefore, is a computationally conservative method of network server data transmission rate selection that selects transmission rates that are suitable for a plurality of network clients exhibiting heterogeneous reception bandwidth and useful with unicast and multicast data delivery mechanisms.